In constructing a telecom network, a designer is faced with the task of selecting network node locations (i.e., facilities, network nodes, cabinets . . . etc.) that serve as many subscriber locations (i.e., homes) as possible, while minimizing the construction and installation costs and maintaining the quality of the transmitted signals. This problem is derived from those commonly referred to as the "p-median location-allocation problem" or the "maximal covering location-allocation problem." In general, the p-median problem is to select p network nodes from among m candidate locations to serve n demand locations, in such a way that the aggregate service distance/time/cost for the n demand locations is minimized. The maximum covering problem, however, is to ensure that the number of demand locations served by the selected p network nodes is maximized.
Location-allocation problems are often solved with the use of heuristic algorithms, the most common type of which is the interchange algorithm. An interchange algorithm involves cycles of repetitive substitutions and comparisons to determine an optimum set of network node locations and corresponding subscriber locations. Examples of current interchange algorithms can be found in a paper authored by Teitz, M. B. and Bart, P., entitled "Heuristic methods for estimating the generalized vertex median of a weighted graph," Operations Research 16: 955-61 (1968), a paper authored by Goodchild, M. F. and Noronha, V. T., entitled "Location-allocation for small computers," Monograph 8, Dept. of Geography, the University of Iowa (1983) and a paper authored by Densham, P. J. and Rushton, G., entitled "A more efficient heuristic for solving large P-median problems," Papers in Regional Science 71, 3: 307-29 (1992).
Although current algorithms are capable of minimizing distances in a network design, they do not provide or suggest a method to account for maximum capacity limits of a network node location. That is to say, these interchange algorithms do not take into account the fact that each network node can only service a limited number of homes. This factor is particularly important in dense regions where there is greater demand (i.e., homes, subscriber premises, etc.). Network nodes selected to service such dense regions will experience a higher demand than other network nodes in the system. This results in unbalanced loads among the network nodes, and such loads often exceed the maximum capacity limit of a real-world network node.
For instance, in the location of CATV cabinets and allocation of homes to such cabinets, each cabinet has a maximum capacity limit, typically sixty-four homes per cabinet (i.e., a limited number of ports to connect to homes). Exceeding the maximum capacity limit requires additional equipment and, thus, results in a non-cost-effective CATV system.
Another approach to the workload problem of facilities is disclosed in a paper authored by Densham, P. J., and Rushton, G., entitled "Providing spatial decision support for rural public service facilities that require a minimum workload" (1996). This approach provides an improved algorithm which is utilized after running a p-median algorithm (as described above) and which adjusts the work load of each network node by reassigning demand among the network nodes in order to meet a required minimum workload for all network nodes. Although such a method can be extended to solve maximum capacity limit problems, this post-processing adjustment is limited by the selected locations of network nodes that do not account for the capacity constraints, and sometimes is not able to redistribute exceeded workloads among the selected network nodes due to full capacity.
Current approaches also do not suggest or provide a method for minimizing street crossings (i.e., minimizing the number of street crossings between a network node location and a corresponding subscriber location over the entire network). In constructing a network, each street crossing increases the overall cost of the network system. The problem appears when cables must be laid under the streets which require additional equipment and labor.
Accordingly, it is an object of the invention to provide a method for designing a telecom network with a minimum number of street crossings.
It is a further object of the invention to provide a method for designing a telecom network that meets the maximum capacity constraints on the network nodes.
Another object of the invention is to provide an easy method for incorporating a variety of constraints in the design of an optimum telecom network.